﻿#include <iostream>

static int merge(int* arr, const int left, const int middle, const int right) {
    size_t arrSize = right - left + 1;
    int* sortArr = (int*)malloc(arrSize*sizeof(int));
    memset(sortArr, 0, arrSize*sizeof(int));
    
    int p1 = left;
    int p2 = middle + 1;
    int sum = 0;
    int index = 0;

    while (p1 <= middle && p2 <= right) {
        sum += arr[p1] < arr[p2] ? (right - p2 + 1) * arr[p1] : 0;
        sortArr[index++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }

    while (p1 <= middle) {
        sortArr[index++] = arr[p1++];
    }

    while (p2 <= right) {
        sortArr[index++] = arr[p2++];
    }

    free(sortArr);
    return sum;
}

static int process(int* numbers, const int left, const int right) {
    if (left == right) return 0;

    int middle = left + ((right - left) >> 1);
    return process(numbers, left, middle) +
            process(numbers, middle + 1, right) +
            merge(numbers, left, middle, right);
}

// 小和问题，就是在一个数组中，依次求和每一个位置的数字的左侧比它小的数字，
// 比如 [1,3,4,2,6], 1是第一个数字，所以没有小和产生；3左侧只有1比它小，故+1；4左侧，1,3比它小，故+1，+3；
// 2左侧，1比它小，故+1；6左侧，1,3,4,2都比它小，故+1,+3,+4,+2
// 最终解是1+1+3+1+1+3+4+2=16
int main_SmallSum() {
    int arr[] = {1, 3, 4, 2, 6, 9};
    size_t size = sizeof(arr)/sizeof(int);
    int sum = process(arr, 0, size - 1);
    printf("%d\n", sum);

    return 0;
}